package com.future;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * Description: 409. 最长回文串
 * 给定一个包含大写字母和小写字母的字符串s，返回通过这些字母构造成的 最长的回文串。
 * <p>
 * 在构造过程中，请注意 区分大小写 。比如"Aa"不能当做一个回文字符串。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/longest-palindrome
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author weiruibai.vendor
 * Date: 2022/11/17 10:45
 */
public class Solution_409 {

    static Solution_409 instance = new Solution_409();

    public static void main(String[] args) {

        String s = "abccccdd";
        s = "abccccdd";
        s = "aaaaaccc";
        s = "bb";
        System.out.println(instance.longestPalindrome(s));
    }

    /**
     * 偶数都能满足
     * 奇数留最大，剩下的长度大于1就删掉一个成为偶数
     *
     * @param s
     * @return
     */
    public int longestPalindrome(String s) {
        Map<Character, Integer> map = new HashMap<>();
        for (Character ch : s.toCharArray()) {
            map.put(ch, map.getOrDefault(ch, 0) + 1);
        }
        int ans = 0;
        PriorityQueue<Integer> queue = new PriorityQueue<>(((o1, o2) -> o2 - o1));
        for (Map.Entry<Character, Integer> m : map.entrySet()) {
            if (m.getValue() % 2 != 0) {
                queue.add(m.getValue());
            } else {
                ans += m.getValue();
            }
        }
        if (!queue.isEmpty()) {
            ans += queue.poll();
        }
        while (!queue.isEmpty()) {
            int val = queue.poll();
            if (val > 1) {
                ans += val - 1;
            }
        }
        return ans;
    }
}
